This is the first application filed for the present invention.
Not applicable.
The present invention relates to multi-stage switches, and in particular to a method and apparatus for mapping high bandwidth connections through a multi-stage switch.
Synchronous Optical Network (SONET)/Synchronous Digital Hierarchy (SDH) protocol is widely used for physical-layer data transport. SDH is the European equivalent of the SONET standard. A reference in this document to SONET is therefore intended to refer to SDH as well as SONET. Under the SONET protocol, signals are forwarded section-by-section across a network along an end-to-end connection (i.e. a SONET path), which is established (nailed up) prior to a communications session, and which remains nailed-up for at least the duration of the session.
As is well known in the art, it is highly desirable to successfully complete every request for a path through a telecommunications network. A path that cannot be completed successfully, for example because a connection between sections of the path cannot be found, is said to be xe2x80x9cblockedxe2x80x9d. It is also well known that a plurality of switch nodes can be interconnected in a multi-stage architecture to provide a Clos network. Application Specific Integrated Circuits (ASICs) can also be interconnected in a Clos network pattern within a SONET switch to provide a versatile switching node.
It is also known that a Clos network may be designed to be non-blocking by providing sufficient hardware resources. For example, a three-stage Clos-type network can be made non-blocking by providing a sufficiently large number of nodes in the center stage. In particular, a three-stage Clos network supporting P input connections into the ingress stage, and M connections through the center stage, can be made completely non-blocking by providing that Mxe2x89xa72Pxe2x88x921. However, as the required number of input connections increases, the number of connections through the center stage required for a non-blocking network (and the associated cost) becomes prohibitive. Accordingly, various techniques have been employed to reduce the probability of blocking in a switch that is of a manageable size. The primary techniques include xe2x80x9cpackingxe2x80x9d and xe2x80x9cre-orderingxe2x80x9d.
xe2x80x9cPackingxe2x80x9d refers to a technique of mapping connections through a switch (between an ingress node and an egress node) in which the system attempts to map each new connection through the most heavily utilized center stage node. If that attempt fails (due to inadequate idle capacity in the selected center stage node), then successive attempts are made to map the new connection through progressively less utilized center stage nodes, until either a center stage node with sufficient idle capacity is found, or it is determined that the new connection cannot be mapped through the network (in which case the connection is xe2x80x9cblockedxe2x80x9d). This technique has proven satisfactory for low-bandwidth connections (i.e. having an STS-1 granularity, for example). However, the probability of blocking increases rapidly as the connection bandwidth increases.
Re-ordering refers to a method of mapping connections through a switch network in which, if a new connection is initially blocked (e.g. following a packing algorithm described above), it may nevertheless still be mapped through the network if previously-mapped connections can be rearranged. An example of this method is provided in U.S. Pat. No. 5,987,027, which issued to Park et al. on Nov. 16, 1999. Re-ordering connections can reduce the probability of blocking of new connections, even in cases where the granularity exceeds STS-1. However, a significant amount of system overhead is required to re-order existing connections without interrupting associated communications sessions. As a result, the time required to map new connections increases dramatically as each successive connection is mapped through the switch network.
An alternative method of mapping connections through a switch network is referred to as xe2x80x9cbit-slicingxe2x80x9d, in which a signal is divided into a number of fixed-size units that are evenly distributed across the center stage. Every center stage node handles its respective unit in an identical manner to map the signal to the egress node, and thus a connection map of each center stage node of the switch network is identical. This arrangement tends to simplify the control signaling within the switch network, but dramatically reduces the routing flexibility. Additionally, because the number of units must be equal to the number of center stage nodes (or an integer multiple thereof), the size of each unit must necessarily vary with the signal bandwidth. For example, a switch network having 12 center stage nodes can map an STS-12 signal by slicing that signal into 12 units, each of which having an STS-1 granularity. An STS-48 signal can also be mapped by slicing into 12 units, but in this case each unit must have an STS-4 granularity. Since modern networks commonly carry signal traffic having varying bandwidths, the ingress stage must have some means of controlling the slicing of incoming signals to produce and route units of the appropriate size. This requirement greatly increases the complexity and cost of the switch network.
Accordingly, a method and apparatus that enables connections for high bandwidth signals to be rapidly mapped through a Clos network, with a low probability of blocking and high utilization efficiency of network resources, remains highly desirable.
An object of the present invention is to provide a method an apparatus for mapping high bandwidth connections through a Clos network or a Clos-type versatile switch.
Accordingly, an aspect of the present invention provides method of mapping a connection for a high bandwidth signal through a Clos network between an ingress node and an egress node via a center stage comprising a plurality of center stage nodes. A number of units in the high bandwidth signal is determined. Each of the units has an equal predetermined size. A number of available connections through the Clos network equal to the number of units is then located. Finally, each unit is mapped to a respective one of the available connections across a center stage node to the egress node of the Clos network mapping each unit to a respective one of the identified available connections, so that the units are generally unequally distributed across each center stage node, but a sum of all signals switched through the Clos network from the ingress node to the egress node at any given time is substantially equally distributed across the center stage nodes of the Clos network.
A further aspect of the present invention provides a Clos network adapted to map a connection for a high bandwidth signal between an ingress node and an egress node via a center stage having a plurality of center stage nodes. The Clos network comprises: means for determining a number of units of the high bandwidth signal, each of the units having an equal predetermined size; locating means adapted to locate a number of available connections through the Clos network equal to the number of units; and, means for mapping each unit to a respective one of the identified available connections, wherein the units are unequally distributed across the center stage nodes, but a sum of all signals switched through the Clos network from said ingress to said egress at any one time is substantially equally distributed across the center stage nodes of the Clos network.
In embodiments-of the invention, the high bandwidth signal is a SONET/SDH signal. The SONET/SDH signal is an STS-N signal comprising N STS-1 frames, and the number of units of the high bandwidth signal corresponds with the number of frames of the STS-N signal. The value of N may be two or more.
The Clos network may be represented by a matrix of connections between the ingress node and the center stage. Each column of the matrix represents a link between the ingress node and a respective center stage node. Each row of the matrix represents connections between the ingress node and each of the center stage nodes. The available connections may be located by successively selecting each connection within a row of the connection matrix. An availability of each selected connection is then determined, and a count of available connections incremented when a selected connection is determined to be available. The count is reset to zero when the selected connection is determined to be unavailable. These steps are repeated until a first predetermined termination condition is satisfied.
The connection matrix is preferably a representation of connections through the Clos-network, that is used to facilitate mapping of signals. The relationship between connections represented in the connection matrix and physical I/O connections within the Clos-network may be arbitrary.
A connection may be determined to be available if a unit of another high bandwidth signal has not previously been mapped to the connection; and the connection can be mapped through a respective center stage node to the egress node. Otherwise, the connection is determined to be unavailable.
A location of a first, available connection may be stored when the count of available connections is incremented to a value of one.
The first predetermined termination condition may comprise any one of: the accumulated count of available connections is equal to the number of units; and a last connection within a row is selected and the accumulated count of available connections is less than the number of units.
When a last connection within a row is selected and the accumulated count of available connections is less than the number of units, a determination may be made concerning whether the matrix contains a next successive row. If a next successive row exists, the process of locating available connections can continue within the successive row. Alternatively, if a next successive row does not exist, a blocking condition of the high bandwidth signal may be reported.
Each unit of the high bandwidth signal may be mapped across the Clos network by mapping each successive unit of the high bandwidth signal to a respective one of the located available connections. Each respective connection, to which a unit has been mapped, is then mapped through a respective center stage node to the egress node.
An advantage of the present invention is that high bandwidth signal paths can be rapidly mapped through the multi-stage switch with high efficiency of utilization of the switch capacity, and low probability of blocking.